import java.util.ArrayDeque;
import java.util.Deque;

// 227. 基本计算器 II
class Solution {
    public int calculate(String ss) {
        Deque<Integer> dq = new ArrayDeque<>();
        int n = ss.length();
        char[] ch = ss.toCharArray();
        int i = 0; // 用于遍历 ch
        char op = '+'; // 用于保存运算符
        while (i < n) {
            if (ch[i] == ' ') i++;
            else if (ch[i] >= '0' && ch[i] <= '9') {
                int tmp = 0;
                while (i < n && ch[i] >= '0' && ch[i] <= '9') {
                    tmp *= 10;
                    tmp += ch[i] - '0';
                    i++;
                }
                if (op == '-') dq.push(-tmp);
                else if (op == '+') dq.push(tmp);
                else if (op == '*') dq.push(dq.pop() * tmp);
                else dq.push(dq.pop() / tmp);
            }
            else {
                op = ch[i];
                i++;
            }
        }
        int ret = 0;
        while (!dq.isEmpty()) {
            ret += dq.pop();
        }
        return ret; 
    }
}